home *** CD-ROM | disk | FTP | other *** search
/ Best Objectech Shareware Selections / UNTITLED.iso / boss / word / text / 024 / findrep.c < prev    next >
C/C++ Source or Header  |  1993-06-04  |  49KB  |  1,631 lines
  1. /*******************  start of original comments  ********************/
  2. /*
  3.  * Written by Douglas Thomson (1989/1990)
  4.  *
  5.  * This source code is released into the public domain.
  6.  */
  7.  
  8. /*
  9.  * Name:    dte - Doug's Text Editor program - find/replace module
  10.  * Purpose: This file contains the functions relating to finding text
  11.  *           and replacing text.
  12.  *          It also contains the code for moving the cursor to various
  13.  *           other positions in the file.
  14.  * File:    findrep.c
  15.  * Author:  Douglas Thomson
  16.  * System:  this file is intended to be system-independent
  17.  * Date:    October 1, 1989
  18.  */
  19. /*********************  end of original comments   ********************/
  20.  
  21. /*
  22.  * The search and replace routines have been EXTENSIVELY rewritten.  The
  23.  * "brute force" search algorithm has been replaced by the Boyer-Moore
  24.  * string search algorithm.  This search algorithm really speeds up search
  25.  * and replace operations.
  26.  *
  27.  *                  Sketch of the BM pattern matching algorithm:
  28.  *
  29.  *    while (not found) {
  30.  *       fast skip loop;    <===  does most of the work and should be FAST
  31.  *       slow match loop;   <===  standard "brute force" string compare
  32.  *       if (found) then
  33.  *          break;
  34.  *       shift function;    <===  mismatch, shift and go to fast skip loop
  35.  *    }
  36.  *
  37.  * See:
  38.  *
  39.  *   Robert S. Boyer and J Strother Moore, "A fast string searching
  40.  *     algorithm."  _Communications of the ACM_ 20 (No. 10): 762-772, 1977.
  41.  *
  42.  * See also:
  43.  *
  44.  *   Zvi Galil, "On Improving the Worst Case Running Time of the Boyer-
  45.  *    Moore String Matching Algorithm."  _Communications of the ACM_
  46.  *    22 (No. 9): 505-508, 1979.
  47.  *
  48.  *   R. Nigel Horspool, "Practical fast searching in strings." _Software-
  49.  *    Practice and Experience_  10 (No. 3): 501-506, 1980.
  50.  *
  51.  *   Alberto Apostolico and Raffaele Giancarlo, "The Boyer-Moore-Galil
  52.  *    String Searching Strategies Revisited."  _SIAM Journal on Computing_
  53.  *    15 (No. 1): 98-105, 1986.
  54.  *
  55.  *   Andrew Hume and Daniel Sunday, "Fast String Searching."  _Software-
  56.  *    Practice and Experience_ 21 (No. 11): 1221-1248, November 1991.
  57.  *
  58.  *   Timo Raita, "Tuning the Boyer-Moore-Horspool String Searching Algorithm."
  59.  *    _Software-Practice and Experience_ 22 (No. 10): 879-884, October 1992.
  60.  *
  61.  *
  62.  *                            Boyer-Moore in TDE
  63.  *
  64.  * Hume and Sunday demonstrated in their paper that using a simple shift
  65.  * function after a mismatch gives one of the fastest search times with the
  66.  * Boyer-Moore algorithm.  When searching normal text for small patterns
  67.  * (patterns less than 30 characters or so), Hume and Sunday found that the
  68.  * faster the algorithm can get back into the fast skip loop with the
  69.  * largest shift value then the faster the search.  Some algorithms can
  70.  * generate a large shift value, but they can't get back into the skip loop
  71.  * very fast.  Hume and Sunday give a simple method for computing a shift
  72.  * constant that, more often than not, is equal to the length of the search
  73.  * pattern.  They refer to the constant as mini-Sunday delta2 or md2.  From
  74.  * the end of the string, md2 is the first leftmost occurrence of the
  75.  * rightmost character.  Hume and Sunday also found that using a simple string
  76.  * compare as the match function gave better performance than using the C
  77.  * library memcmp( ) function.  The average number of compares in the slow
  78.  * loop was slightly above 1.  Calling the memcmp( ) function to compare 1
  79.  * character slows down the algorithm.  See the Hume and Sunday paper for an
  80.  * excellent discussion on fast string searching.  Incidentally, Hume and
  81.  * Sunday describe an even faster, tuned Boyer-Moore search function.
  82.  *
  83.  * Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a bug when
  84.  * building the ignore skip index array in TDE 1.3 and previous versions.
  85.  * BTW, I added assertions to those functions that build the skip index
  86.  * array to make certain that everything is everything.
  87.  *
  88.  * The Boyer-Moore search algorithm in TDE was rearranged so that it is now
  89.  * almost identical to the original version Boyer-Moore described in CACM.
  90.  * The simple shift function in TDE was replaced by the mini-delta2 shift
  91.  * function in the Hume and Sunday paper.
  92.  *
  93.  * I am not very fond of WordStar/TURBO x style search and replace prompting,
  94.  * which is used in the DTE 5.1 editor.  Once the search pattern has been
  95.  * defined, one only needs to press a key to search forwards or backwards.
  96.  * The forward or backward search key may be pressed at any time in any file
  97.  * once the pattern has been entered.  Also, the search case may be toggled
  98.  * at any time in any file once the pattern has been entered.
  99.  *
  100.  * New editor name:  TDE, the Thomson-Davis Editor.
  101.  * Author:           Frank Davis
  102.  * Date:             June 5, 1991, version 1.0
  103.  * Date:             July 29, 1991, version 1.1
  104.  * Date:             October 5, 1991, version 1.2
  105.  * Date:             January 20, 1992, version 1.3
  106.  * Date:             February 17, 1992, version 1.4
  107.  * Date:             April 1, 1992, version 1.5
  108.  * Date:             June 5, 1992, version 2.0
  109.  * Date:             October 31, 1992, version 2.1
  110.  * Date:             April 1, 1993, version 2.2
  111.  * Date:             June 5, 1993, version 3.0
  112.  *
  113.  * This modification of Douglas Thomson's code is released into the
  114.  * public domain, Frank Davis.   You may distribute it freely.
  115.  */
  116.  
  117. #include "tdestr.h"
  118. #include "common.h"
  119. #include "tdefunc.h"
  120. #include "define.h"
  121.  
  122.  
  123. /*
  124.  * Name:    get_replacement_flags
  125.  * Purpose: To input find and replace flags.
  126.  * Date:    June 5, 1991
  127.  * Passed:  line:  prompt line
  128.  * Returns: OK if flags were entered, ERROR if user wanted to abort
  129.  */
  130. int  get_replacement_flags( int line )
  131. {
  132. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  133. register int c;
  134. int  func;
  135. int  rc;
  136.  
  137.    save_screen_line( 0, line, line_buff );
  138.    eol_clear( 0, line, g_display.text_color );
  139.    /*
  140.     * options: prompt or no prompt (p/n)?
  141.     */
  142.    s_output( find1, line, 0, g_display.message_color );
  143.    xygoto( strlen( find1 ) + 2, line );
  144.    do {
  145.       c = getkey( );
  146.       func = getfunc( c );
  147.    } while (c != 'P'  &&  c != 'p'  &&  c != 'N'  &&  c != 'n'  &&
  148.             c != RTURN  &&  c != ESC  &&  func != AbortCommand);
  149.    restore_screen_line( 0, line, line_buff );
  150.    switch (c) {
  151.       case 'P' :
  152.       case 'p' :
  153.       case RTURN :
  154.          g_status.replace_flag = PROMPT;
  155.          rc = OK;
  156.          break;
  157.       case 'N' :
  158.       case 'n' :
  159.          g_status.replace_flag = NOPROMPT;
  160.          rc = OK;
  161.          break;
  162.       default :
  163.          rc = ERROR;
  164.    }
  165.    bm.search_defined = rc;
  166.    return( rc );
  167. }
  168.  
  169.  
  170. /*
  171.  * Name:    ask_replace
  172.  * Purpose: Ask user if he wants to (r)place, (s)kip, or (e)xit.
  173.  * Date:    June 5, 1991
  174.  * Returns: TRUE if user wants to replace, ERROR otherwise.
  175.  * Passed:  window:   pointer to current window
  176.  *          finished: TRUE if user pressed ESC or (e)xit.
  177.  */
  178. int  ask_replace( WINDOW *window, int *finished )
  179. {
  180. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  181. register int c;
  182. int  func;
  183. int  prompt_line;
  184. int  rc;
  185.  
  186.    prompt_line = window->cline - 1;
  187.    c = 39 - (strlen( find2 ) >> 1);
  188.    save_screen_line( 0, prompt_line, line_buff );
  189.    /*
  190.     * replace skip exit (r/s/e)?
  191.     */
  192.    s_output( find2, prompt_line, c, g_display.message_color );
  193.    do {
  194.       c = getkey( );
  195.       func = getfunc( c );
  196.    } while (c != 'R' && c != 'r' && c != 'S' && c != 's' && c != 'E' && c != 'e'
  197.           && c != ESC  &&  func != AbortCommand);
  198.    restore_screen_line( 0, prompt_line, line_buff );
  199.    switch (c) {
  200.       case 'R' :
  201.       case 'r' :
  202.          rc = OK;
  203.          break;
  204.       case 'E' :
  205.       case 'e' :
  206.          *finished = TRUE;
  207.       case 'S' :
  208.       case 's' :
  209.          rc = ERROR;
  210.          break;
  211.       default :
  212.          *finished = TRUE;
  213.          rc = ERROR;
  214.          break;
  215.    }
  216.    return( rc );
  217. }
  218.  
  219.  
  220. /*
  221.  * Name:    ask_wrap_replace
  222.  * Purpose: After a wrap, ask user if he